package com.leecode;

import com.test.TreeNode;

import java.util.*;

/**
 * 按层,从左到右遍历,层序遍历,典型的bfs
 */
public class Leet102 {
	public static void main(String[] args) {
		TreeNode treeNode = new TreeNode<Integer>(1);
		treeNode.right = new TreeNode<Integer>(3);
		new Leet102().levelOrder(treeNode);
	}

	public List<List<Integer>> levelOrder(TreeNode<Integer> root) {
		List<List<Integer>> list = new ArrayList();
		int n = 0;
//		dfs(root,n,list);
		bfs(root, list);
		return list;
	}

	/**
	 * 我用dfs遍历树,只不过找到了往大list加数据的特点,完成这题,但没有真正掌握bfs!!!
	 *
	 * @param tn
	 * @param n    第一层list[0],第二层list[1],...
	 * @param list 大list很好理解,因此有recur,所以一直往下面传
	 */
	public void dfs(TreeNode<Integer> tn, int n, List<List<Integer>> list) {
		if (tn == null) return;

		if (list.size() == n) {
			List<Integer> l = new ArrayList<>();
			l.add(tn.val);
			list.add(l);
		} else {
			list.get(n).add(tn.val);
		}

		dfs(tn.left, n + 1, list);
		dfs(tn.right, n + 1, list);
	}

	/**
	 * 先放头(第一层),弹出头并不急着删了头,而是利用头,把头的left和头的right加入(第二层)
	 * 弹出头的left,加入两个,弹出头的right,加入两个,共加入4个(相当于第三层)
	 *
	 * @param tn
	 * @param list
	 */
	public void bfs(TreeNode<Integer> tn, List<List<Integer>> list) {
		if (tn == null) return;

//		Queue<TreeNode> queue=new ArrayDeque();//不能add null,一想到队列就想到ArrayQueue也是有毒,这个类,各种null不让加
		Queue<TreeNode> queue = new LinkedList();//没仔细看吧,既是List也是Queue,可以add null
		queue.add(tn);
		while (!queue.isEmpty()) {
			int temp = queue.size();
			List l = new ArrayList<Integer>();
			for (int a = 0; a < temp; a++) {
				TreeNode poll = queue.poll();
				if (poll != null) {
					l.add(poll.val);//poll 几个小list就add几个
				} else {
					l.add(null);//
				}
				//[1,null,3],Queue弹出1,意味着要加入null,3
				//头空就不加,头不是空且存在(左子or右子)
				if (poll != null && (poll.left != null || poll.right != null)) {
//					//ArrayDeque的add方法参数@NotNull,
					queue.add(poll.left);//left maybe null
					queue.add(poll.right);
				}

			}

			list.add(l);
		}
	}
}
